package 期末复习;

import java.util.*;

public class 贪心算法解决背包问题 {
     //1.定义背包的最大容量，物品的重量，物品的价值
    private int MAX_WEIGHT = 150;//定义背包的容量
    private int[] weights = new int[]{35, 30, 60, 50, 40, 10, 25};//物品的重量
    private int[] values = new int[]{10, 40, 30, 50, 35, 40, 30};//物品的价值

    private void packageGreedy(int capcity,int[] weights,int[] values){
        int n=weights.length;
        double[] r=new double[n];
        int[] index=new int[n];
        for(int i=0;i<n;i++){
            r[i]=(double)values[i]/weights[i];
            index[i]=i;
        }
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if(r[i]<r[j]){
                    double temp=r[i];
                    r[i]=r[j];
                    r[j]=temp;
                    int x=index[i];
                    index[i]=index[j];
                    index[j]=x;
                }
            }
        }

        int[] w1=new int[n];
        int[] values1=new int[n];
        for(int i=0;i<n;i++){
            w1[i]=weights[index[i]];
            values1[i]=values[index[i]];
        }
        System.out.println("按照性价比排序的物品的重量为：");
        for(int v:w1){
            System.out.print(v+"\t");
        }
        System.out.println();
        System.out.println("按照性价比排序的物品的价值为：");
        for(int b:values1){
            System.out.print(b+"\t");
        }
        System.out.println();
        int[] flag=new int[n];
        int maxValue=0;
        for(int i=0;i<n;i++){
            if(w1[i]<=capcity){
                flag[i]=1;
                capcity-=w1[i];
                maxValue+=values1[i];
            }
        }

        System.out.println("背包放入物品的情况为："+Arrays.toString(flag));
        System.out.println("背包的最大价值为："+maxValue);
    }

    public static void main(String[] args) {
        贪心算法解决背包问题 p = new 贪心算法解决背包问题();
        p.packageGreedy(p.MAX_WEIGHT,p.weights,p.values);
    }






    /*private void packageGreedy(int capcity, int[] weights, int[] values) {//capcity表示背包的剩余容量
        //2.创建一个物品性价比的数组并赋值
        int n = weights.length;
        double[] r = new double[n];//创建一个性价比数组
        int[] index = new int[n];//按性价比排序物品的下标
        for (int i = 0; i < n; i++) {
            r[i] = (double) values[i] / weights[i];//计算每件物品的性价比并存入数组当中
            index[i] = i;//一开始使用的默认下标
        }

        //3.交换元素的值和交换物品下标的值
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {//j从i+1开始
                if (r[i] < r[j]) {
                    double temp = r[i];
                    r[i] = r[j];
                    r[j] = temp;//元素的值交换
                    int x = index[i];
                    index[i] = index[j];
                    index[j] = x;//数组下标进行交换
                }
            }
        }

        //4.创建两个按照性价比排序的物品的重量数组和价值数组
        int[] w1 = new int[n];
        int[] value1 = new int[n];

        for (int i = 0; i < n; i++) {
            w1[i] = weights[index[i]];//将按性价比排序后物品的重量存入新的数组中
            value1[i] = values[index[i]];//将按性价比排序后物品的价值存入新的数组中
        }

        //5.打印输出按照性价比排序好的重量数组和价值数组
        System.out.println("按照性价比排序后存放重量的数组为：");//使用增强for循环打印出按照性价比排序后的物品重量和价值数组
        for (int v : w1) {
            System.out.print(v + "\t");
        }
        System.out.println();
        System.out.println("按照性价比排序后存放价值的数组为：");
        for (int i : value1) {
            System.out.print(i + "\t");
        }
        System.out.println();

        //6.创建一个状态数组用来记录该物品是否被放入到了背包中
        int[] flag = new int[n];
        int maxValue = 0;
        for (int i = 0; i < n; i++) {
            if (w1[i] <= capcity) {//如果要放入的物品的重量小于背包的总容量就放入
                flag[i] = 1;//将放入的物品的状态置为1
                capcity -= w1[i];//背包装入物品后剩余的容量
                maxValue += value1[i];//背包的最大价值


            }
        }

        //7.最后打印输出哪些物品放入了背包并输出背包的最大价值
        System.out.println("放入的物品的情况为：" + Arrays.toString(flag));//打印输出哪些物品放入到了背包中
        System.out.println("最大价值为：" + maxValue);

    }

    public static void main(String[] args) {
        贪心算法解决背包问题 p = new 贪心算法解决背包问题();
        p.packageGreedy(p.MAX_WEIGHT, p.weights, p.values);

    }*/
}
